'''
Created on 2012-9-24

@author: infear
'''
class Solution(object):
    def __init__(self):
        self.boatlist=[];
        self.distance=[];
    
    #has checked
    def add(self,boat):
        self.boatlist.append(boat);
        #print boat.x,boat.y;
        self.distance.append([]);
        
    def _print(self):
        for boat in self.boatlist:
            print "(x:%d,y:%d)" %(boat.x,boat.y);
        for i in self.distance:
            print i;
        
    def ConnectedByIsland(self,boat1,boat2):
        if boat1==boat2:
            return True;
        x1=float(boat1.x);
        y1=float(boat1.y);
        x2=float(boat2.x);
        y2=float(boat2.y);
        x0=y0=200.0;
        radius=50;
        try:
            a=(y2-y1)/(x2-x1);
            b=-1;
            c=(y1*x2-y2*x1)/(x2-x1);
        except ZeroDivisionError:
            a=1;
            b=0;
            c=-x1;
        distance=abs(a*x0+b*y0+c)/((a*a+b*b)**0.5);
        if radius<distance:
            return True;
        else:
            root_x=(b*b*x0-a*c-a*b*y0)/(a*a+b*b);
            root_y=(a*a*y0-a*b*x0-b*c)/(a*a+b*b);
            if(root_x-x1)*(root_x-x2)<0 and (root_y-y1)*(root_y-y2)<0:
                return False;
            else:
                return True;
    
    def ConnectedByBoat(self,boat1,boat2,boat3):
        if boat1.index==boat2.index or boat1.index==boat3.index or boat2.index==boat3.index:
            return True;
        x1,y1,x2,y2,x3,y3=float(boat1.x),float(boat1.y),float(boat2.x),float(boat2.y),float(boat3.x),float(boat3.y);
        if((y2-y3)*(x1-x2)==(y1-y2)*(x2-x3)):
            if((y3-y1)*(y3-y2)<=0 and (x3-x2)*(x3-x1)<=0):
                return False;
            else:
                return True;
        else:
            return True;

    def initDistance(self):       
        for b1 in self.boatlist:
            for b2 in self.boatlist:
                flag1=self.ConnectedByIsland(b1,b2);
                if not flag1:
                    print b1.index,b2.index,"blocked by island!"
                flag2=True;
                for b3 in self.boatlist:
                    if not self.ConnectedByBoat(b1, b2, b3):
                        flag2=False;
                        print b1.index,b2.index,"blocked by boat:",b3.index
                        break;
                if flag1 and flag2:
                    self.distance[b1.index].append(1);
                else:
                    self.distance[b1.index].append(0);
        
        
    def findShortestPath(self):
        start,end=0,len(self.boatlist)
        _result,_list=[[start]],[start];
        self.boatlist[start].visit=False;
        while len(_list)!=0:
            st=_list.pop();
            for i in range(0,end):
                if(self.distance[st][i]==1 and self.boatlist[i].visit==False):
                    self.boatlist[i].visit=True;
                    for j in _result:
                        if j[len(j)-1]==st:
                            _t=j+[i]; 
                            _result.append(_t);
                            if(i==end-1):
                                return _t; 
                            break;
                    _list.append(i);
     
                       
    
                        
                